%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%12pt: grandezza carattere
                                        %a4paper: formato a4
                                        %openright: apre i capitoli a destra
                                        %twoside: serve per fare un
                                        %   documento fronteretro
                                        %report: stile tesi (oppure book)
\documentclass[12pt,a4paper,openright,oneside]{report}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%libreria per scrivere in italiano
\usepackage[italian]{babel}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%libreria per accettare i caratteri
                                        %   digitati da tastiera come ? ?
                                        %   si puo' usare anche
                                        %   \usepackage[T1]{fontenc}
                                        %   pero' con questa libreria
                                        %   il tempo di compilazione
                                        %   aumenta
\usepackage[utf8]{inputenc}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%libreria per impostare il documento
\usepackage{fancyhdr}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%libreria per avere l'indentazione
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   all'inizio dei capitoli, ...
\usepackage{indentfirst}
%
%%%%%%%%%libreria per mostrare le etichette
%\usepackage{showkeys}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%libreria per inserire grafici
\usepackage{graphicx}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%libreria per utilizzare font
                                        %   particolari ad esempio
                                        %   \textsc{}
\usepackage{newlfont}
\usepackage{amsfonts}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%librerie matematiche
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{amsthm}
\usepackage{textcomp}
\usepackage{eurosym}
\usepackage{listings}
\usepackage{rotating}



\def\lstlanguagefiles{lst-grafite.tex}
\lstset{language=grafite}
%
\newcommand{\lsem}{[\![}
\newcommand{\rsem}{]\!]}


\oddsidemargin=30pt \evensidemargin=20pt%impostano i margini
\hyphenation{sil-la-ba-zio-ne pa-ren-te-si}%serve per la sillabazione: tra parentesi 
					   %vanno inserite come nell'esempio le parole 
%					   %che latex non riesce a tagliare nel modo giusto andando a capo.

%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%comandi per l'impostazione
                                        %   della pagina, vedi il manuale
                                        %   della libreria fancyhdr
                                        %   per ulteriori delucidazioni
\pagestyle{fancy}\addtolength{\headwidth}{20pt}
\renewcommand{\chaptermark}[1]{\markboth{\thechapter.\ #1}{}}
\renewcommand{\sectionmark}[1]{\markright{\thesection \ #1}{}}
\rhead[\fancyplain{}{\bfseries\leftmark}]{\fancyplain{}{\bfseries\thepage}}
\cfoot{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\linespread{1.3}                        %comando per impostare l'interlinea
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%definisce nuovi comandi
%
%\lstset{basicstyle=\small\ttfamily}
%\lstset{keywordstyle=\color{black}\bfseries}
%\lstset{commentstyle=\color{darkgrey},}
%\lstset{stringstyle=\color{black}}
%\lstset{showstringspaces=true}



\begin{document}




\begin{titlepage}
\begin{center}
{{\Large{\textsc{Alma Mater Studiorum $\cdot$ Universit\`a di
Bologna}}}} \rule[0.1cm]{15.8cm}{0.1mm}
\rule[0.5cm]{15.8cm}{0.6mm}
{\small{\bf FACOLT\`A DI SCIENZE MATEMATICHE, FISICHE E NATURALI\\
Corso di Laurea Magistrale in Informatica}}
\end{center}
\vspace{15mm}
\begin{center}
{\LARGE{\bf Algoritmi Avanzati}}\\
\end{center}
\vspace{40mm}
\par
\hfill
\begin{center}
 {\large{\bf Jacopo Baldassarri}}
\end{center}
\vspace{20mm}
\begin{center}
{\large{\bf Anno Accademico 2011/2012}}
\end{center}
\end{titlepage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%non numera l'ultima pagina sinistra
\clearpage{\pagestyle{empty}\cleardoublepage}
\tableofcontents                        %crea l'indice
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%imposta l'intestazione di pagina
\rhead[\fancyplain{}{\bfseries\leftmark}]{\fancyplain{}{\bfseries\thepage}}
\lhead[\fancyplain{}{\bfseries\thepage}]{\fancyplain{}{\bfseries
INDICE}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%non numera l'ultima pagina sinistra
\pagenumbering{roman}                   %serve per mettere i numeri romani
\chapter*{\begin{description}
 \item 
\end{description}
Introduzione}                 %crea l'introduzione (un capitolo
                                        %   non numerato)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%imposta l'intestazione di pagina
\rhead[\fancyplain{}{\bfseries
INTRODUZIONE}]{\fancyplain{}{\bfseries\thepage}}
\lhead[\fancyplain{}{\bfseries\thepage}]{\fancyplain{}{\bfseries
INTRODUZIONE}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%aggiunge la voce Introduzione
                                        %   nell'indice
\addcontentsline{toc}{chapter}{Introduzione}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Parleremo di algoritmi paralleli che possono essere distindi in diverse categoria, come spiegato in figura.
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{Intro/Intro.eps}
\caption[Intro]{Algoritmi Paralleli}\label{Intro}
\end{center}
\end{figure}

\section{Memoria Comune}
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{Intro/Memoria_Comune.eps}
\caption[Memoria Comune]{Memoria Comune}\label{Memoria Comune}
\end{center}
\end{figure}
In questo tipo di architettura abbiamo dei problemi di accesso (concorrenza).\\
In presenza di processori sincroni abbiamo un ''ente globale'' che coordina tutti i processori, può essere vista come una macchina di Von Neumann parallela.
Il modello PRAM è un modello teorico perchè al livello attuale della tecnologia non è realizzabile in concreto in modo efficiente. Ci serve per capire se un problema 
è inerentemente sequenziale e quindi non abbiamo grossi vantaggi in parallelo. In presenza del modello CONCORRENTE, avremo bisogno di primitive di sincronizzazione
per evitare l'inconsistenza dei dati.

\section{Memoria Locale}
\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm]{Intro/Memoria_Locale.eps}
\caption[Memoria Locale]{Memoria Locale}\label{Memoria Locale}
\end{center}
\end{figure}
Nella memoria di un processore può scrivere solo il suo processore, ma possono leggere anche altri processori, con una organizzazione ad albero.
\begin{figure}[h]
\begin{center}
\includegraphics[width=5cm]{Intro/Albero.eps}
\caption[Albero]{Albero}\label{Albero}
\end{center}
\end{figure}
\newpage
\section{Master Theorem}
$$T(n)=aT(n/b)+cn^\beta\hspace{3cm}\beta\geq0\hspace{1cm}a\geq1\hspace{1cm}b\geq2$$
In cui abbiamo che:
\begin{itemize}
 \item $n$ è la dimensione del problema
 \item $a$ è il numero di chiamate ricorsive
 \item $b$ è il numero di parti in cui si divide il problema
 \item $n^\beta$ rappresenta il tempo per dividere in sotto problemi e per poi ricomporlo
\end{itemize}
A questo punto confrontiamo $\alpha$ e $\beta$ per capire la complessità del nostro problema:
$$\alpha = \frac{\log a}{\log b}$$
Se abbiamo che:
\begin{itemize}
 \item $\alpha > \beta$ soluzione $O(n^\alpha)$
 \item $\alpha = \beta$ soluzione $O(n^\alpha \log n)$
 \item $\beta > \alpha$ soluzione $O(n^\beta)$
\end{itemize}


\clearpage{\pagestyle{empty}\cleardoublepage}
\chapter{Algoritmi PRAM}                %crea il capitolo
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%imposta l'intestazione di pagina
\lhead[\fancyplain{}{\bfseries\thepage}]{\fancyplain{}{\bfseries\rightmark}}
\pagenumbering{arabic}                  %mette i numeri arabi

Vogliamo calcolare la sommatori di $n$ numeri $a_1, a_2, ..., a_n$ contenuti in un vettore $a[1...n]$:
\begin{lstlisting}[language=grafite]
function SOMMATORIA (a[1...n], n): integer
    var $i, b$: integer;
    begin
      $b:=a[1]$;
      for $i:=1$ to $n$ do
        $b:=b+a[i]$;
      return $b$;
    end;
\end{lstlisting}

La computazione avviene nel modo seguete:
$$((...((a[1]+a[2])+a[3])+...)+a[n-1])+a[n]$$
però sappiamo che per la proprietà associativa della somma potrebbe anche procedere in modo diverso, assumendo $n$ pari:
$$(a[1]+a[2])+(a[3]+a[4])+...+(a[n-1]+a[n])$$
Se avessimo $n/2$ processori, potremmo eseguire simultaneamente ciascuna somma $a[i]+a[i+1]$, per ogni $i$ dispari, potrebbe essere eseguita in tempo costante
contemporaneamente alle altre. Iterando quindi il procedimento e dimezzando sempre più la dimensione del problema, potremmo calcolare la sommatoria in un tempo 
totale $O(\log n)$ che sarebbe un netto miglioramento rispetto al tempo $O(n)$ che è necessario per calcolare la stessa somma della funzione sopra citata.\\
Il modello più semplice di computazione parallela è detto PRAM (''Parallel Random Access Machine'') in cui abbiamo più processori sincroni, cioè che condividono
lo stesso ciclo di clock e una memoria globale condivisa fra tutti i processori. Il modello ha le seguenti caratteristiche principali:
\begin{itemize}
\item Ogni processore esegue la stessa istruzione ma su dati diversi.
\item Possiamo far lavorare un sottoinsieme di processori mentre alcuni restano inattivi.
\item Ogni processore attivo è sincronizzato, l'istruzione successiva non può iniziare finchè tutti non hanno concluso l'istruzione corrente.
\item La memoria è utilizzata dai processori per scambiarsi dati in $O(1)$ tempo.
\end{itemize}
Utilizzeremo il seguente costrutto per esprimere l'esecuzione in parallelo di istruzioni:
\begin{center}
 \textbf{for all} $i$ \textbf{where} $inf \leq i \leq sup$ \textbf{do in parallel} operazione$_i$
\end{center}
si esegue contemporaneamente operazione$_i$ per ogni $i$ compreso fra i due estremi $inf$ e $sup$.
Esistono diverse varianti del modello PRAM, in base alla possibilità, da parte dei processori, di leggere/scrivere la memoria contemporaneamente:
\begin{itemize}
\item EREW (''Exclusive Read Exclusive Write'') non è consentito ne la scrittura ne la lettura contemporanea.
\item CREW (''Concurrent Read Exclusive Write'') è possibile leggere contemporaneamente ma non scrivere.
\item CRCW (''Concurrent Read Concurrent Write'') è possibile sia leggere che scrivere contemporaneamente.
\end{itemize}

\section{Sommatoria}
Vogliamo quindi calcolare la sommatoria utilizzando un algoritmo parallelo; assumiamo per semplicità che  la dimensione dell'input $n$ sia una potenza di 2 (è comunque
sempre possibile renderlo tale, aggiungendo degli 0 all'input) e che i numeri siano elencati $a_n, a_{n+1},...,a_{2n-1}$. Possiamo immaginarci che ogni numero $a_i$
sia memorizzato in una foglia di un albero binario completo di $2n-1$ nodi, indicizzati come uno heap, in cui la radice ha indice 1 e i figli di un nodo $i$
hanno rispettivamente indice $2i$ per il figlio sinistro e $2i+1$ per il figlio destro. Partendo dal penultimo livello a salire, considerando tutti i nodi di uno
stesso livello, possiamo calcolare in $a_i$ la somma dei suoi figli $a_{2i}$ e $a_{2i+1}$ che corrisponde alla sommatoria dei numeri che si trovano nelle foglie del
sotto albero radicato nel nodo $i$, per $1\leq i \leq n-1$.Abbiamo quindi la nostra funzione che diventa nel modo seguente:
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{PRAM/Albero_Sommatoria.eps}
\caption[Albero Sommatoria]{Albero Sommatoria}\label{Albero Sommatoria}
\end{center}
\end{figure}
\newpage
\begin{lstlisting}
function SOMMATORIA $(a[n..2n-1], n)$: integer
begin
  for $k := log n-1$ downto 0 do
    for all $i$ where $2^k\leq i \leq 2^{k+1}-1$ do in parallel
        $a[i]:=a[2i]+a[2i+1]$;
    SOMMATORIA:=$a[1]$
end;
\end{lstlisting}
Possiamo vedere che il \textbf{for} esterno viene ripetuto $O(\log n)$ volte, mentre il \textbf{for all} interno richiede tempo $O(1)$, abbiamo 
quindi una complessit\`a della funzione SOMMATORIA pari a $O(\log n)$ con un numero di processori utilizzati pari a $O(n)$. Possiamo a questo 
punto per\`o notare che ogni algoritmo parallelo, impiega un ammontare di lavoro L, che rappresenta il tempo richiesto se lo stesso algoritmo
fosse eseguito in maniera sequenziale usando un singolo processore, dato dal prodotto di P (numero di processori) per T (tempo). Nel caso 
dell'algoritmo sopra, il nostro lavoro \`e quindi $O(n \log n)$ che \`e peggiore di quello del migliore algoritmo sequenziale che \`e $O(n)$.
Dobbiamo quindi modificare il nostro algoritmo parallelo in modo da avere un lavoro pari almeno a $O(n)$. Possiamo ridurre il numero di processori
dividendo il nostro input in $O(n/\log n)$ parti di dimensione $O(\log n)$ elementi e facendo sommare ad ogni processore in modo sequenziale
i numeri di ogni parte. In questo modo il  nostro problema originario \`e stato ridotto in tempo $O(\log n)$ ed usando $O(n/\log n)$ processori
ad un problema pi\`u piccolo di dimensione $O(n/\log n)$. Al problema cos\`i modificato possiamo quindi applicare la funzione SOMMATORIA che a
questo punto richiede $O(\log (n/\log n))$ tempo usando $O(n/\log n)$ processori, ottenendo un lavoro ottimo pari a $O(n)$.
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{PRAM/Sommatoria_Migliore.eps}
\caption[Sommatoria Ottima]{Sommatoria Ottima}\label{Sommatoria Ottima}
\end{center}
\end{figure}
Gli elementi da sommare sono indicati con $a_n,a_{n+1},...,a_{2n-1}$. Viene eseguita una prima fase dove ogni processore somma sequenzialmente 
gli elementi di un gruppo di $\log n$ elementi. Poi viene fatta la sommatoria parallela degli $n/\log n$ elementi che contengono i risultati 
della prima fase. Si usa un vettore $a[1...2n-1]$ dove gli elementi da sommare sono memorizzati in $a[n...2n-1]$ ed il risultato in $a[1]$. 
Ottenendo cos\`i un lavoro ottimo pari a $O(n)$.
\begin{lstlisting}
procedure SOMMATORIA $(a[n..2n-1], n)$: integer
begin
  for all $j$ where $1\leq j \leq n/\log n$ do in parallel begin
      $a[n/\log n+j-1]:=a[n+(j-1)\log n];$
      for $i:=1$ to $\log n-1$ do
	  $a[n/\log n+j-1]:=a[n/\log n+j-1]+a[n+(j-1)\log n+i]$;
  end;
  for $k:=\log (n/\log n)-1$ downto 0 do
      for all $j$ where $2^k \leq j \leq 2^{k+1}-1$do in parallel
	  $a[j]:=a[2j]+a[2j+1]$;
end;
\end{lstlisting}

\section{Somme Prefisse}
Prendiamo ora in considerazione un problema simile al precedente della sommatoria di $n$ numeri.
Dati $n$ numeri interi $a_1,a_2,...,a_n$ calcolare tutte le somme parziali $b_i=\begin{matrix} \sum_{j=1}^i a_j \end{matrix}$ per $i=1,2,...,n$.
Utilizzeremo come in precedenza un input che possiamo sempre considerare di dimensioni potenza di due e che i numeri siano indicati con 
$a_n,a_{n+1},...,a_{2n-1}$ sempre memorizzati nelle foglie di un albero binario completo di $2n-1$ nodi realizzato con un vettore $a[2n-1]$.
Viene prima fatta una fase ascendente  in cui si esegue la stessa computazione della funzione SOMMATORIA, mettendo il risultato in $b_1$. Poi viene
fatta una fase discendente in cui si calcola il valore $b_i$ di ogni altro nodo nel seguente modo: il $b_i$ di un figlio destro \`e uguale a quello 
del padre, mentre il $b_i$ di un figlio sinistro \`e uguale a quello del padre meno il valore $a_{i+1}$ del fratello per $2 \leq i \leq 2n-1$.
Otterremo in questo modo  che il valore $b_i$ di un nodo sar\`a sempre uguale alla somma degli $a_j$ dei nodi che sono allo stesso livello di $b_i$
e che hanno come indice $j$  minore o uguale ad $i$. Quindi $b_{n+1}=a_n+a_{n+1}+...+a_{n+i}$ come volevamo ottenere.
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{PRAM/SommePrefisse.eps}
\caption[Albero Somme Prefisse]{Albero Somme Prefisse}\label{Albero Somme Prefisse}
\end{center}
\end{figure}
\begin{lstlisting}
procedure SOMMEPREFISSE$(a[n...2n-1],b[n...2n-1])$: integer
  begin
    $b[1]:= SOMMATORIA(a[n...2n-1],n)$;
    for $k:=1$ to $\log n$ do
	for all $i$ where $2^k \leq i \leq 2^{k+1}-1$ do in parallel
	    if $odd(i)$
		then $b[i]:=b[(j-1)/2]$
		else $b[i]:=b[i/2]-a[i+1]$;
  end;
\end{lstlisting}
Possiamo vedere che la complessit\`a della procedura \`e $O(\log n)$ e vengono utilizzati $O(n)$ processori che possono per\`o essere ridotti ad
$O(n/\log n)$ usando il metodo visto in precedenza per la sommatoria,  ottenendo cos\`i un lavoro ottimo pari a $O(n)$.

\section{Ordinamento}
Veniamo quindi ad uno dei pi\`u classici dei problemi, il problema dell'ordinamento di $n$ numeri distinti $a_1,a_2,...,a_n$.
Possiamo progettare un algoritmo detto ''torneo'' per risolvere il problema. Confrontiamo ogni numero $a_i$ con tutti gli altri numeri e 
andiamo a contare quante volte esso risulta essere ''perdente'' (minore o uguale $a_i$ incluso) oppure ''vincente'' (maggiore). Il numero di
volte che l'elemento risulta essere perdente ci dice in che posizione deve stare.
\begin{lstlisting}
procedure TORNEO$(a[1...n],n)$: integer
  begin
    for all $i,j$ where $1\leq i,j\leq n$ do in parallel
	if $a[i]\leq a[j]$ then $V[i,j]:=1$ else $v[i,j]:=0$;
    for all $j$ where $1\leq j \leq n$ do in parallel
	$P[j]:=SOMMATORIA(j-esima\ colonna\ di\ V,n)$;
    for all $j$ where $1\leq j \leq n$ do in parallel 
	$a[P[j]]:=a[j]$;
  end;
\end{lstlisting}
La procedura ha complessit\`a $O(\log n)$ utilizzando per\`o $n^2$ processori in un modello CREW. Se volessimo utilizzare un modello EREW
dovremmo evitare che si verifichino conflitti in lettura sulla stessa cella di memoria, il generico elemento $a[i]$, per ciascun $1\leq i \leq n$,
\`e coinvolto in $n$ istruzioni diverse di confronto allo stesso momento dentro al primo \textbf{for} dove viene confrontato con $a[j]$, lo
stesso tipo di problema ovviamente si verifica anche per $a[j]$ stesso. Possiamo risolvere il problema facendo $n$ copie di ciascun $a[i]$ ed
$n$ copie di ciascun $a[j]$ in tempo $O(\log n)$, in modo che gli $n^2$ processori possano accedere in lettura in tempo $O(1)$ ad un unica coppia
di valori $a[i]$ e $a[j]$.\\
Possiamo quindi vedere una procedura che risolve questo problema, effettua $n$ copie di un dato $d$ mettendole negli $n$ elementi di un vettore $copia[1...n]$:
\newpage
\begin{lstlisting}
procedure REPLICA$(copia[1...n],d,n)$:integer
  begin
    $copia[1]:=d;$
    for $k:=0$ to $\log n-1$ do
	for all $i$ where $1 \leq i \leq 2^k $ do in parallel
	    $ copia[i+2^k]:= copia[i]$;
  end;
\end{lstlisting}
La procedura REPLICA richiede tempo $O(\log n)$ ed $O(n)$ processori. Possiamo quindi richiamarla in parallelo $2n$ volte ed effettuare $n$ copie di ciascun $a[i]$
e di ciascun $a[j]$ in tempo $O(\log n)$ usando $O(n^2)$ processori. Infine la procedura TORNEO può essere eseguita con il modello EREW sempre in tempo $O(\log n)$ ma
usando solo $O(n^2/\log n)$ processori. Il lavoro della nuova versione della procedura TORNEO risulta pertanto essere $O(n^2)$ che è comunque peggiore del lavoro
ottimo $O(n\log n)$ del miglior algoritmo sequenziale.

\section{Elaborazione di Puntatori}
Riconsideriamo il problema delle SOMMEPREFISSE dove gli $n$ dati sono memorizzati questa volta in una lista e l'ordine col quale calcolarne le somme prefisse è 
determinato da come tali dati sono tra loro concatenati nella lista tramite i puntatori. Indichiamo con $a[i]$ il valore della lista gestito dal processore i-esimo
e con $succ[i]$ il cursore all'elemento successivo della lista, dove inizialmente $succ[i]=0$ se e solo se $a[i]$ è l'ultimo valore della lista.
\begin{lstlisting}
procedure SOMMEPREFISSE $(a[1...n],b[1...n],succ[1...n],n)$:integer
  begin
    for all $i$ where $ 1 \leq i\leq n$ do in parallel
	$b[i]:=a[i]$;
    for $k:=1$ to $\lceil\log n\rceil$ do
	for all $i$ where $1 \leq i \leq n$ do in parallel
	    if $succ[i]\neq0$ then begin
		$b[succ[i]]:=b[i]+b[succ[i]]$;
		$succ[i]:=succ[succ[i]]$
	    end
  end
\end{lstlisting}
La tecnica utilizzata nel \textbf{for all} interno è detta ''pointer jumping''. Si osservi che non si verificano mai dei conflitti da parte di più processori per
accedere alla stessa locazione di memoria. Infatti per $i\neq j$ abbiamo sempre che $succ[i]\neq succ[j]$ oppure $succ[i]=succ[j]=0$ che viene mantenuto per tutta
l'esecuzione della procedura. Possiamo quindi usare un modello EREW e la procedura richiede tempo $O(\log n)$ usando $n$ processori.
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{PRAM/Salto_Puntatori.eps}
\caption[Salto Puntatori]{Salto Puntatori}\label{Salto Puntatori}
\end{center}
\end{figure}
Il lavoro della procedura è $O(n\log n)$ che non è ottimo, ma questo può essere abbassato ad un lavoro ottimo di $O(n)$ con un algoritmo piuttosto complicato che 
non verrà riportato qua.\\
Vediamo un altro esempio di utilizzo della tecnica del ''pointer jumping'' per calcolare il livello dei nodi di un albero binario realizzato con puntatori. Combineremo 
tale tecnica con la tecnica del ''ciclo Euleriano''. Ricordiamo che un ''ciclo Euleriano''  di un grafo orientato $G$ è un ciclo che include ogni arco una ed una sola 
volta e che $G$ contiene un ciclo Euleriano se e solo se è connesso e per ciascun nodo il numero di archi entranti è uguale al numero di archi uscenti.
Per  calcolare la profondità di un albero binario B di $n$ nodi, si considera un ciclo Euleriano del grafo orientato $B'$ ottenuto da $B$, dove tale ciclo è rappresentato 
con una lista mono direzionale di $3n$ elementi sulla quale viene applicata la tecnica del salto dei puntatori. Ogni nodo $u$ di $B$ è sostituito con tre elementi di una lista,
che individuiamo con $x,y,z$ in modo che i risultanti $3n$ elementi siano gestiti ciascuno da uno ed un solo processore.
\begin{itemize}
 \item l'elemento $x$ del nodo $u$ vale +1 e punta all'elemento $x$ del figlio sinistro di $u$, se esiste, oppure all'elemento $y$ di $u$ stesso, altrimenti;
 \item l'elemento $y$ del nodo $u$ vale 0 e punta all'elemento $x$ del figlio destro di $u$, se esiste, oppure all'elemento $z$ di $u$ stesso, altrimenti;
 \item l'elemento $z$ del nodo $u$ vale -1 e punta all'elemento $y$ del padre di $u$, se $u$ è un figlio sinistro, oppure all'elemento $z$ del padre di $u$, se $u$ è
un figlio destro, oppure a 0, se $u$ è la radice. 
\end{itemize}
La lista inizia con l'elemento $x$ della radice e termina con l'elemento $z$ della radice. La lista può essere costruita in tempo costante $O(1)$, eseguendo la 
procedura SOMMEPREFISSE su tale lista, è facile vedere che l valore $b$ di ciascun elemento $z$ rappresenta il livello del corrispondente nodo $u$. Quindi i livelli
dei nodi di $B$ possono essere calcolati in tempo $O(\log n)$ usando $O(n)$ processori.
\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm]{PRAM/Ciclo_Euleriano.eps}
\caption[Ciclo Euleriano]{Ciclo Euleriano}\label{Ciclo Euleriano}
\end{center}
\end{figure}

\section{Valutazione di Polinomi}
Dato un polinomio nella forma $p(x)=a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+...+a_1x+a_0$ vogliamo valutarlo in un punto preciso $q$, cioè vogliamo calcolare $p(q)$ nel modello
EREW.\\
Procediamo calcolando inizialmente le potenze $q^0,...,q^{n-2},q^{n-1}$ di $q$, dato che il generico $q^i=qq^{i-1}$ con $1\leq i \leq n-1$, si considerano i prodotti 
prefissi $b$ del vettore $x$ contenente un 1 seguito da $n-1$ copie di $q$. Infine si calcolano i prodotti $a_iq^i$ per $0\leq i \leq n-1$ nel vettore $r$ in cui poi 
verrà effettuata la sommatoria.
\begin{lstlisting}
function VALUTAPOLINOMIO $(a[1...n],x[1...n],q)$:real
  begin
    COPIA $(q,n,x)$;
    $x[1]:=1;$
    PRODOTTIPREFISSI$(x,n)$;
    for all $j$ where $0\leq j \leq n/\log n-1 $ do in parallel
	for $ i:=0 $ to $ \log n-1$ do
	    $r[n+j*n/\log n+i]:=a[j*n/\log n+i]*b[n+j*n/\log n+i]$;
    SOMMATORIA $(r,n)$;
    VALUTAPOLINOMIO $:=r[1]$;
end;
  
\end{lstlisting}

\section{Punto Interno ad un Poligono}
Dato un generico poligono vogliamo sapere se questo è convesso oppure no.
\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm]{PRAM/Poligoni.eps}
\caption[Poligoni]{Poligoni}\label{Poligoni}
\end{center}
\end{figure}
Forniamo una rappresentazione del poligono elencando i suoi vertici in ordine orario/antiorario e specificando le coordinate di ogni vertice: $V_i=(x_i,y_i)$. 
Consideriamo ora un generico punto del poligono e per vedere se questo è convesso, tracciamo la perpendicolare al punto e considerando solo la parte superiore andiamo
a contare le volte che la perpendicolare interseca i lati del poligono. Se la perpendicolare interseca i lati del poligono un numero pari di volte allora il punto è
esterno al poligono e quindi esso non è convesso, altrimenti se la perpendicolare interseca i lati del poligono un numero dispari di volte, il punto è interno e il 
poligono è convesso.\\
La procedura andrà a considerare in parallelo tutti i lati del poligono e se questi sono nella parte superiore alla perpendicolare, andrà a vedere se intersecano la 
retta perpendicolare. Usiamo un vettore di $n$ elementi, pari ai lati del poligono, di valori booleani e se interseca la perpendicolare lo imposto ad 1 altrimenti lo
lascio a 0; una volta considerati tutti i lati vado a fare la somma dei valori booleani del vettore per vedere se ho ottenuto un numero di intersezioni pari oppure
dispari.

\section{AND di valori}
Vogliamo calcolare l'AND di $n$ valori booleani di un vettore.\\ Consideriamo un modello CRCW, assumendo che se più processori vogliono scrivere la stessa locazione di 
memoria, uno solo riuscirà effettivamente a farlo.
\begin{lstlisting}
procedure AND-CRCW $(b[1...n])$:boolean;
  begin
    $x:=true$;
    for all $j$ where $q\leq j \leq n$ do in parallel 
      if not $b[j]$ then $x:=false$;
    AND-CRCW$:=x$;
  end;
\end{lstlisting}
Il primo processore che riuscirà a scrivere effettivamente $false$ nella locazione di memoria $x$ farà in modo che la procedura restituisca appunto $false$ dato che 
basta che uno degli $n$ valori sia $false$ per fare si che tutto l'AND restituisca $false$.\\
Otteniamo così un tempo $T=O(1)$, un numero di processori pari a $P=O(n)$ per un lavoro ottimo $L=O(n)$, anche se allo stato attuale delle tecnologia è impossibile
realizzare un modello che permette la scrittura in memoria in tempo $O(1)$.

\section{La Tesi della Computazione Parallela}
Abbiamo visto come l'introduzione di più processori che lavorano in parallelo possa abbassare radicalmente la complessità in tempo di alcuni problemi. Una legittima
aspirazione sarebbe quella di di risolvere in tempo polinomiale con algoritmi paralleli problemi che sono intrattabili con algoritmi sequenziali.\\
La Tesi della Computazione Parallela asserisce che ogni problema risolvibile in tempo polinomiale con un algoritmo parallelo può essere risolto in spazio polinomiale
con un algoritmo sequenziale. Come si ignora se P=NP oppure no, così neanche si conosce se P-SPAZIO=P, dove P-SPAZIO è la classe dei problemi intrinsecamente 
superpolinomiale. Abbiamo quindi questo problema, anche se è opinione comune che P-SPAZIO contenga problemi di complessità intrinsecamente superpolinomiale e che 
quindi problemi intrattabili sequenzialmente restino tali anche in parallelo.\\ 
La classe dei problemi che si ritiene trattabili è detta NC e, come conseguenza della Tesi della Computazione Parallela, si ha che NC coincide con la classe di problemi
P che sono risolubili con una quantità di memoria che è $O(\log^k n)$ con $k$ costante. I problemi che abbiamo visto nella parte precedente sono tutti problemi  in NC.\\
Come si ignora se P=NP, così non si conosce se P=NC. Se si trovasse un algoritmo parallelo con complessità temporale polilogaritmica che utilizzi una quantità di
processori polinomiale per un solo problema Log-Spazio-completo (un problema in P è detto Log-Spazio-completo se ogni altro problema in P è riducibile ad esso con una
trasformazione che richiede spazio polilogaritmico), allora se ne potrebbero trovare per tutti i problemi in P e quindi risulterebbe P=NC.
\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm]{PRAM/Relazioni_di_Contenimento.eps}
\caption[Relazioni di Contenimento]{Relazioni di Contenimento di Problemi}\label{Relazioni di Contenimento}
\end{center}
\end{figure}


\chapter{Algoritmi per Reti a Grado Limitato}
Abbiamo appena visto il modello PRAM che però resta un modello teorico, data l'impossibilità di realizzazione con le tecnologie attuali. In pratica perch\`e  un modello 
parallelo sincrono sia effettivamente realizzabile occorre che la memoria no sia affatto globale e che i processori comunichino fra loro soltanto attraverso una prefissata 
rete di interconnessione. Tale rete è rappresentata con un grafo non orientato, i cui nodi corrispondono ai processori e i cui archi sono le interconnessioni fra i
processori. I processori possono così comunicare in tempo $O(1)$ se e solo se c'è un arco che li collega. Dobbiamo dire però che una rete affinch\`e sia effettivamente
costruibile non può essere un grafo completo! In pratica abbiamo che, detto $g$ il grafo massimo di dei nodi, cioè il numero massimo di archi incidenti in un nodo,
dobbiamo avere che $g$ sia ''piccolo'', possibilmente limitato da una costante. Dati due processori la loro distanza è rappresentata dal numero minimo di archi tra tutte
le catene che li uniscono, ed il diametro $d$ della rete è uguale alla distanza massima tra tutte le coppie di processori.
Vedremo di seguito alcune architetture di reti, mesh, shuffle, butterfly ed ipercubi e analizzeremo poi alcuni problemi utilizzando tali reti, mostrando come questi
problemi possano essere risolti in tempo ottimo come nel modello PRAM.

\section{Reti di interconnessione}
Considereremo quattro diverse architetture di reti di interconnessione che sono la mash, la shuffle, la butterfly e l'ipercubo. Vediamole ora in dettaglio.
\subsection{Mesh}
Una mesh quadrata gli $n$ processori, con $n=p^2$ per $p$ intero positivo, sono organizzati in una matrice quadrata di dimensione $\sqrt{n} \times \sqrt{n}$ in cui un
generico processore $P_{i,j}$, con $1\leq i, j\leq \sqrt{n}$, è connesso con i processori $P_{i,j\pm 1}$ e $P_{i\pm 1,j}$. Il grado massimo di ogni nodo $g$ è 4 mentre 
il diametro $d$ della mesh è pari a $\sqrt{n}$.
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{RETI/Mesh.eps}
\caption[Mesh]{Mesh con $n=16$ processori}\label{Mesh}
\end{center}
\end{figure}
Esistono anche delle versioni alternative alla classica mesh: la mesh ciclica, dove sono connessi ta loro anche il primo e l'ultimo processore di ogni riga/colonna e
la mesh toroidale, in cui l'ultimo processore di ogni riga/colonna è connesso con il primo processore della riga/colonna successiva.

\subsection{Shuffle}
In una shuffle gli $n$ processori, con $n=2^p$ per $p$ intero positivo, sono numerati da 0 a $2^p-1$ e vi sono due tipi di connessioni fra i processori. Le connessioni
di scambio non orientate sono tra i processori $P_i$ e $P_{i+1}$ per ogni $i$ pari, mentre le connessioni di mescolamento orientate escono dal processore $P_i$ per
$o\leq i \leq n-2$ ed entrano nel processore $P_j$, dove $j=2i\ mod\ (n-1)$, con un ulteriore connessione da $P_{n-1}$ a se stesso.\\ 
Possiamo vedere come percorrendo le connessioni di mescolamento $p=\log n$ volte a partire da $P_i$ per $1\leq i \leq n-2$ si ritorna al processore $P_i$ stesso. Usando 
anche le connessioni di scambio è anche possibile raggiungere un qualsiasi altro processore in $O(\log n)$ passi. Abbiamo qui un grado massimo $g$ pari a 3 ed un diametro
$d$ pari a $O(\log n)$.
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{RETI/Shuffle.eps}
\caption[Shuffle]{Shuffle con $n=8$ processori}\label{Shuffle}
\end{center}
\end{figure}

\subsection{Butterfly}
In una butterfly di grado $k$, gli $n$ processori, con $n=(k+1)2^k$ per $k$ intero positivo, sono disposti in $k+1$ righe e $2^k$ colonne, in cui il generico elemento
$P_{i,j}$, con $1\leq i \leq k, 0 \leq j \leq 2^k -1$, è connesso con i processori $P_{i-1,j}$ e $P_{i-1,m}$, dove $m$ è l'intero ottenuto complementando l'i-esimo bit
più significativo della rappresentazione binaria di $j$. Abbiamo in questo caso un grado massimo $g$ di ogni nodo pari a 4 ed un diametro $d$ pari a $O(k)=O(\log n)$.
Possiamo anche notare che i processori della riga 0 (o della riga $k$) possono essere visti come le foglie comuni a $2^k$ alberi binari completi le cui radici sono i 
processori della riga $k$ (o della riga 0).
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{RETI/Butterfly.eps}
\caption[Butterfly]{Butterfly con rango $k=3$ e $n=(k+1)2^k = 32$ processori}\label{Butterfly}
\end{center}
\end{figure}
\newpage

\subsection{Ipercubo}
In un ipercubo di dimensione $k$ ($k$ intero positivo), abbiamo che gli $n=2^k$ processori sono numerati da 0 a $2^k -1$ ed il generico processore $P_i$ è connesso con 
tutti i processori $P_j$ tali che le rappresentazioni binarie di $i$ e $j$ differiscono per il valore di un singolo bit. Otteniamo qui un grado di ogni dono $g$ ed un
diametro $d$ pari entrambi a $k=\log n$.
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{RETI/Ipercubo.eps}
\caption[Ipercubo]{Ipercubo con dimensione $k=4$ e $n=2^4 = 16$ processori}\label{Ipercubo}
\end{center}
\end{figure}

\section{Sommatoria}
Andiamo ora a vedere come risolvere il problema della sommatoria con le varie reti di interconnessione sopracitate, vedremo prima la procedura
SOMMATORIA-IPERCUBO, la procedura SOMMATORIA-SHUFFLE ed infine la procedura SOMMATORIA-MESH.\\

\subsection{Ipercubo}
Siano $a_o, a_1,..., a_{n-1}$ gli $n$ numeri da sommare, con $n=2^k$ e si consideri un ipercubo di dimensione $k$, tale che il dato $a_i$ sia
contenuto inizialmente nel processore $P_i$, per $0 \leq i \leq n-1$. Consideriamo dapprima gli $n/2$ processori con indici minori (con il bit
pi\`u significativo a 0), i quali individuano un ipercubo di dimensione $k-1$, ed ognuno di essi somma in parallelo il suo dato con quello 
contenuto nel corrispondente processore dell'altro ipercubo di dimensione $k-1$ formato dagli $n/2$ processori con indici maggiori (con il bit
pi\`u significativo ad 1). Il procedimento viene poi iterato considerando gli $n/4, n/8,..., n/n$ processori con indici minori, che corrispondono 
ad ipercubi di dimensione $k-2, k-3,..., 0$, considerando cio\`e gli indici con anche il secondo, terzo,..., ultimo bit pi\`u significativo a 0.
Dopo $k=\log n$ iterazione, il risultato sar\`a ottenuto nel processore $P_0$.
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{RETI/Sommatoria_Ipercubo.eps}
\caption[Sommatoria ipercubo]{Sommatoria eseguita su ipercubo con $k=4$ e $n=2^k=16$ processori}\label{Sommatoria ipercubo}
\end{center}
\end{figure}
Otteniamo la seguente procedura che richiede tempo $O(\log n)$ utilizzando $n$ processori.
\begin{lstlisting}
procedure SOMMATORIA-IPERCUBO $a[0...n-1])$;
  begin
    for $i=\log n$ downto 0 do begin
	$h:=2^i$
	for all $j$ where $0 \leq j \leq h-1 $ do in parallel
	    begin $ b[j] \leftarrow a[j+h]; a[j]:=a[j]+b[j];$ end;
    end;
  end;
\end{lstlisting}
Il lavoro della procedura \`e $O(n\log n)$ che pu\`o comunque essere reso ottimo considerando una sequenza di $O(n\log n)$ elementi da sommare.

\subsection{Shuffle}
Consideriamo ora sempre lo stesso problema prendendo una shuffle di $n=2^k$ processori, assumendo ancora che $a_i$ sia contenuto inizialmente nel 
processore $P_i$, per $0 \leq i \leq n-1$. Consideriamo due procedure ausiliarie SCAMBIA e MESCOLA. La procedura SCAMBIA$(a_i)$ ha come effetto 
quello di scambiare in tempo $O(1)$ gli $a_i$ dei processori di indice pari con quelli dei processori di indice dispari, mentre la procedura 
MESCOLA$(a_i)$ ha l'effetto di spostare in tempo $O(1)$ gli $a_i$ tra i processori in accordo alle connessioni di mescolamento.\\
La procedura risulta essere molto semplice e consiste in $\log n$ chiamate di MESCOLA e SCAMBIA alternate, che utilizzano una sequenza di appoggio
$b_0, b_1,..., b_{n-1}$. Otteniamo cos\`i un tempo di esecuzione $O(\log n)$ utilizzando $n$ processori.
\begin{lstlisting}
procedure SOMMATORIA-SHUFFLE$(a[0...n-1])$;
  begin
    for $i$ to $\log n$ do
      for all $j$ where $o \leq j \leq n-1$ do in parallel
	  MESCOLA$(a[j])$;
	  $b[j]:=a[j]$;
	  SCAMBIA$(b[j])$;
	  $a[j]:=a[j]+b[j]$
      end
  end;
\end{lstlisting}
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{RETI/Sommatoria_Shuffle.eps}
\caption[Sommatoria shuffle]{Sommatoria eseguita su shuffle}\label{Sommatoria huffle}
\end{center}
\end{figure}

\subsection{Mesh}
Risolviamo infine il problema della sommatoria usando una rete di interconnessione a mesh quadrata. Siano $a_{1,1},..., a_{1,p},a_{2,1},..., a_{2,
p},..., a_{p,1},..., a_{p,p}$ gli $n=p^2$ elementi da sommare, tali che $a_{i,j}$ sia contenuto inizialmente nel processore $P_{i,j}$, per
$1 \leq i, j\leq \sqrt{n}$. Partiamo sommando gli elementi dell'ultima riga agli elementi della penultima riga, poi andremo  a sommare gli elementi
della penultima a quelli della terzultima riga, risalendo cos\`i fino alla prima riga, dove verranno poi sommati i risultati parziali da destra
verso sinistra, ottenendo cos\`i il risultato nel processore $P_{1,1}$.
\begin{lstlisting}
procedure SOMMATORIA-MESH$(a[1,1],a[1,2],...a[p,p])$;
  begin
    for $i:=p-1$ downto 1 do
      for all $i,j$ where $1 \leq j \leq p$ do in parallel
	  begin $b[i,j] \leftarrow a[i+1,j]; a[i,j]:=a[i,j]+b[i,j]$ end;
    for $i:=p-1$ downto 1 do
      for all $i,j$ where $i=1$ do in parallel
	  begin $b[i,j] \leftarrow a[i,j+1]; a[i,j]:=a[i,j]+b[i,j]$ end
  end;
\end{lstlisting}
Il tempo della procedura cos\`i realizzata \`e $O(\sqrt{n}$ utilizzando $n$ processori, ottenendo un lavoro pari a $O(n\sqrt{n}$ che possiamo
rendere ottimo utilizzando una sequenza di elementi da ordinare pari a $O(n\sqrt{n}$.
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{RETI/Sommatoria_Mesh.eps}
\caption[Sommatoria mesh]{Sommatoria eseguita su una mesh}\label{Sommatoria mesh}
\end{center}
\end{figure}

\section{Mergesort Bitonico}
Consideriamo ora un algoritmo per risolvere il problema della sommatoria, ideato da Batcher negli anni '60.\\
Presa una sequenza $a_0, a_1, ..., a_{n-1}$ si dice unimodale se esiste un indice $i$, $0\leq i \leq n-1$, tale che $a_0 \leq a_1 \leq ... \leq 
a_i$ e $ a_i\geq a_{i+1} \geq ... \geq a_{n-1}$.Diremo inoltre che una sequenza \`e bitonica se questa \`e unimodale oppure se \`e ottenibile con
una traslazione ciclica da una sequenza unimodale.\\
La sequenza 2, 6, 7, 8, 10, 3, 1, 0 \`e unimodale e quindi anche bitonica. Consideriamo ora una propriet\`a  importante delle sequenza bitoniche.\\
Presa una sequenza bitonica $A= a_0, a_1, ..., a_{2m-1}$, allora le due sequenze:\\
$A_{\texttt{MIN}}=\texttt{min}\{a_0,a_m\},\texttt{min}\{a_1,a_{m+1}\},...,\texttt{min}\{a_{m-1},a_{2m-1}\}$\\
$A_{\texttt{MAX}}=\texttt{max}\{a_0,a_m\},\texttt{max}\{a_1,a_{m+1}\},...,\texttt{max}\{a_{m-1},a_{2m-1}\}$\\
sono esse stesse bitoniche.\\
Questa propriet\`a ci suggerisce un algoritmo parallelo di tipo ''divide \& impera'' per ordinare una sequenza di $n$  elementi con $n$ potenza di 2.
L'algoritmo consiste, se $n>1$, nel dividere $A$ in $A_{\texttt{MIN}}$ e $A_{\texttt{MAX}}$ e riapplicare ricorsivamente la procedura alle due 
sequenze bitoniche $A_{\texttt{MIN}}$ e $A_{\texttt{MAX}}$. Le relazioni di ricorrenza risultano pertanto:\\
\begin{center}
\begin{tabular}{lc}
 $T(n)=d,$ & $\texttt{per}\ n=1,$\\
 $T(n)=T(n/2)+c,$ & $\texttt{per}\ n>1,$\\
\end{tabular}
\end{center}
dove $c$ e $d$ sono due costanti, e quindi $T(n)$ \`e $O(\log n)$, usando $O(n)$ processori. Una sequenza qualsiasi $A$ di lunghezza $n=2^i$ pu\`o 
essere vista come $n/2$ sequenza bitoniche di lunghezza 2. Una volta che si \`e ordinato in parallelo queste $n/2$ sequenze bitoniche, in modo che 
siano alternate una sequenza crescente ad una sequenza decrescente, si utilizza il fatto che la concatenazione di una sequenza crescente con una 
decrescente forma una sequenza bitonica. In questo modo, si considerano $n/4$ sequenze bitoniche lunghe 4, che vengono ordinate con l'algoritmo per
le sequenze bitoniche, poi $n/8$ sequenze lunghe 8 e cos\`i via, finch\`e si arriva ad ordinare una singola sequenza bitonica lunga $n$.\\
Osserviamo che la costruzione di sequenze bitoniche lunghe $2^{i+1}$ richiede l'ordinamento di sequenza bitoniche lunghe $2^i$, che costa $O(\log 2^i)=O(i)$
tempo. Otteniamo quindi un tempo complessivo di $O(\sum_{i=1}^k i)$, che cresce come $O(\log^2 n)$. Poich\`e il numero massimo di confronti che
vengono eseguiti contemporaneamente \`e $n/2$, il numero di processori richiesto \`e $O(n)$, otteniamo quindi un lavoro pari a $O(n\log^2 n)$, che 
risulta essere decisamente migliore dell'algoritmo TORNEO visto in precedenza.\\
Torna molto utile visualizzare lo screma di computazione dell'algoritmo, come illustrato dalla figura 2.8 per $n=16$. 
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{RETI/Mergesort_Bitonico.eps}
\caption[Mergesort Bitonico]{Computazione dell' algoritmo Mergesort Bitonico}\label{Mergesort Bitonico}
\end{center}
\end{figure}
Le linee orizzontali rappresentano i ''canali''  sui quali transitano da sinistra verso destra gli elementi da ordinare. Le frecce verticali
rappresentano confronti tra coppie di elementi, che entrano da sinistra ed escono da destra, in modo che l'elemento maggiore esca sul canale
indicato dalla freccia ed il minore sul canale indicato dal pallino. Vediamo che l'algoritmo ''mergesort bitonico'' ha $k$ iterazioni (4 nella figura
2.8) e che ogni iterazione $i$, per $1 \leq i \leq k$, richiede proprio $i$ passi per ordinare $n/2^i$ sequenze bitoniche lunghe $2^i$.\\
Riportiamo la procedura dell'algoritmo mergesort bitonico eseguita su di un ipercubo, dove $j$ individua il ''passo'' e l'indice $i$ individua 
l'''iterazione'', come indicato anche nella figura 2.8. Useremo inoltre per comodit\`a una numerazione per l'indice $i$ compresa fra 0 e $k-1$
anzich\`e fra 1 e $k$.
\begin{lstlisting}
procedure BITONIC-MERGESORT-IPERCUBO $(a_0,a_1,...,a_{n-1})$;
  begin
    for $i:=0$ to $k-1$ do
      for $j:=i$ downto 0 do begin
	$d:=2^j$
	for all $h$ where $0 \leq h \leq n-1$ do in parallel begin
	  if $h$ mod $2d < d$ then begin
	    $t_h \leftarrow a_{h+d}$;
	    if $h$ mod $2^{i+2} < 2^{i+2}$ then begin
		$b_h:=\texttt{max}\{a_h,t_h\}$;
		$a_h:=\texttt{min}\{a_h,t_h\}$;
	    end else begin
		$b_h:=\texttt{min}\{a_h,t_h\}$;
		$a_h:=\texttt{max}\{a_h,t_h\}$;
	    end
	  end;
	  if $h$ mod $2d\geq d$ then
	    $a_h\leftarrow b_{h-d}$
	end
      end
  end;
\end{lstlisting}
Possiamo vere come il costo del ''for all'' della procedura resta costante, nella variabile temporanea $t_h$ viene copiato il dato del suo vicino
a distanza d. Gli elementi che vado a confrontare differiscono nel loro indice sempre per un solo bit. L'''if'' finale fa lavorare i processori 
che non hanno lavorato, facendo si che vadano a copiarsi il valore che devono memorizzare.\\
Vediamo di seguito nella figura 2.9 l'esecuzione dell'algoritmo su di un ipercubo di dimensione $k=3$  per ordinare la sequenza di $n=8$ elementi
5,6,3,13,7,10,9,2.
\begin{figure}[h]
\begin{center}
\includegraphics[width=8cm]{RETI/Mergesort_Bitonico_Ipercubo.eps}
\caption[Mergesort Bitonico Ipercubo]{Esecuzione ''Mergesort Bitonico'' su ipercubo con $n=2^k$ con $k=3$ elementi}\label{Mergesort Bitonico Ipercubo}
\end{center}
\end{figure}

\section{Moltiplicazione di matrici}
Riconsideriamo ora il problema della moltiplicazione di due matrici $A=[a_{ij}]$ e $B=[b_{ij}]$ di dimensioni $n\times m$, dove la matrice prodotto 
$C=[c_{ij}]=AB$ \`e tale che $c_{ij}=\sum_{k=1}^n a_{ik}b_{kj}$, per $1 \leq i,\ j\leq n$.

\subsection{Mesh}
Consideriamo una mesh ciclica di dimensioni $n \times n$ e si assuma che le due matrici $A$ e $B$ siano memorizzate nell amesh in modo che il 
processore $P_{ij}$ contenga inizialmente gli elementi $a_{ij}$ e $b_{ij}$ ed al termine della computazione contenga $c_{ij}$. Abbiamo una prima 
fase preparatoria in cui gli elementi della riga $i$-esima  di $A$ sono traslati ciclicamente a sinistra di $i-1$ posizioni, $1 \leq i \leq n$, mentre
gli elementi della colonna $j$-esima di $B$ sono traslati ciclicamente verso l'alto di $j-1$ posizioni, $1\leq j \leq n$. Tali traslazioni hanno 
il compito di fare in modo che nel processore $P_{ij}$ si incontri la coppia di elementi $a_{ik}$ e $b_{kj}$ che servono per il calcolo dell'elemento
risultato $c_{ij}$. Nella seconda fase, che dura $n$ iterazioni, sono eseguiti $n^2$ prodotti per ciascuna iterazione, ed ogni elemento di $A$ e $B$
\`e coinvolto in un solo prodotto per iterazione.
\begin{lstlisting}
procedure MOLTMATRICI-MESH$(A,\ B,\ n)$;
  begin
    for $p:=1$ to $n-1$ do
      for all $i,j$ where $1\leq i,j\leq n$ do in parallel begin
	if $i>p$ then $a_{i,j}\leftarrow a_{i,j+1}$;
	if $j>p$ then $b_{i,j}\leftarrow b_{i+1,j}$
      end;
    for all $i,j$ where $1\leq i,j\leq n$ do in parallel $c_{i,j}:=0$;
    for $q:=1$ to $n$ do
      for all $i,j$ where $1\leq i,j\leq n$  do in parallel begin
	$c_{i,j}:=a_{i,j}\ast b_{i,j}+c_{i,j}$;
	$a_{i,j}\leftarrow a_{i,j+1}$;
	$b_{i,j}\leftarrow b_{i+1,j}$
      end
  end;
\end{lstlisting}
La procedura richiede $O(n)$ tempo ed $n^2$ processori per moltiplicare due matrici $n \times n$, otteniamo quindi un lavoro pari a $O(n^3)$ che
risulta essere lo stesso dell'usuale algoritmo sequenziale.\\
Vediamo ora nella figura 2.10, l'esecuzione dell'algoritmo di moltiplicazione di matrici su una mesh ciclica 3 x 3. Vediamo come nella seconda 
e nella terza immagine viene fotografata la situazione della mesh all'uscita dal primo ''for'' sequenziale, per i valori di $p$ uguali a 1 e 2; 
nella terza e quarta immagine invece vediamo la configurazione della matrice nella seconda fase, all'uscita dal secondo ''for'' sequenziale, per i 
valori di $q$ uguali a 1 e 2 (3 non \`e mostrato).
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{RETI/Moltiplicazione_Matrici_Mesh_Ciclica.eps}
\caption[Moltiplicazione Matrici Mesh Ciclica]{Moltiplicazione matrici su mesh ciclica 3 x 3}\label{Moltiplicazione Matrici Mesh Ciclica}
\end{center}
\end{figure}

\subsection{Ipercubo}
Vediamo ora sempre la procedura di moltiplicazione su matrici eseguita su di un ipercubo di $n^3$ processori, e si assuma che $n=2^h$. Avremo quindi
che gli indici dei processori dell'ipercubo hanno valori compreso tra 0 e $2^{3h}-1$, e la loro rappresentazione in binario consta di $3h$ bit, che
possono essere visti come formati da 3 blocchi di $h$ bit, possiamo cos\`i vedere ogni blocco come la rappresentazioni di 3 diversi  indici del 
processore, che a questo punto possiamo individuare univocamente con una terna di indici $(k,i,j)$.\\
Ciascun processore $P_m$ ha cinque variabili locali $A_m,B_m,C_m,D_m$ ed $E_m$, assumiamo che le due matrici abbiano indici di riga e colonna compresi
tra 0 e $n-1$ anzich\`e 1 ed $n$ e che siano memorizzate nell'ipercubo in modo che il processore $P_m=P_{2^hi+j}=P_{0,i,j}$ contenga inizialmente 
gli elementi $a_{ij}$ e $b_{ij}$ nelle variabili $A_m$ e $B_m$, ed al termine della computazione contenga $c_{ij}$ nella variabile $C_m$, 
per $0\leq i,j\leq n-1$.\\ Abbiamo 3 fasi di esecuzione; nella prima fase i dati vengono distribuiti in tempo $O(\log n)$ a tutti i processori 
dell'ipercubo per mezzo di tre cicli ''for'' effettuati su tutti i bit di ciascuno dei tre ''blocchi''. Gli elementi $a_{ij}$ e $b_{ij}$ sono distribuiti 
a tutti gli $A_m$ e $B_m$ dei processori $P_m=P_{2^{2h}k+2^hj+j}=P_{k,i,j}$ tali che $0\leq k \leq n-1$. Allo stesso modo $a_{ik}$ \`e distribuito a tutti 
gli $A_m$ dei processori $P_m=P_{2^{2h}k+2^hi+j}=P_{k,i,j}$ tali che $0\leq j \leq n-1$, mentre $b_{kj}$ \`e distribuito a tutti i $B_m$ dei 
$P_m=P_{2^{2h}k+2^hi+j}=P_{k,i,j}$ tali che $0\leq i \leq n-1$. In questo modo ciascuno degli $n^3$ processori contiene una una coppia distinta di elementi
della matrici $A$ e $B$ da moltiplicare e per l'esattezza $P_m=P_{2^{2h}k+2^hi+j}=P_{k,i,j}$ contiene $a_{ik}$ e $b_{kj}$. Nella seconda fase poi, sono 
effettuati  in tempo $O(1)$ tutti i prodotti. Infine nella terza fase sono sommati i prodotti sui processori $P_{k,i,j}$ tali che $0\leq k \leq n-1$, 
ottenendo i risultati $c_{ij}$ in tempo $O(\log n)$ nei processori $P_{0,i,j}$.\\
Nella procedura seguente useremo due funzioni ausiliarie, BIT($m,p$), che restituisce il $(p+1)$-esimo bit meno significativo della rappresentazione 
binaria di $m$, per $p \geq 0$, e la funzione COMPLEMENTA($m,p$), che restituisce l'intero ottenuto complementando il $(p+1)$-esimo bit meno 
significativo della rappresentazione binaria di $m$. Sia $m=5$, che in binario \`e 101, allora BIT(5,0)=1, BIT(5,1)=0 e BIT(5,3)=0, invece 
COMPLEMENTA(5,0)=4, COMPLEMENTA(5,1)=7.
\begin{lstlisting}
procedure MOLTMATRICI-IPERCUBO$(A,B,n)$;
  begin
    for $p:=3h-1$ downto 2h do
      for all $m$ where BIT$(m,p)=1$ do in parallel
	begin
	  $D_m:=$COMPLEMENTA$(m,p)$;
	  $A_m \leftarrow A_{D_m}$;
	  $B_m \leftarrow B_{D_m}$
	end;
    for $p:=h-1$ downto 0 do
      for all $m$ where BIT$(m,p)\neq\ $BIT$(m,2h+p)$ do in parallel
	begin
	  $D_m:=$COMPLEMENTA$(m,p)$;
	  $A_m \leftarrow A_{D_m}$
	end;
    for $p:=2h-1$ downto $h$ do
      for all $m$ where BIT$(m,p) \neq$ BIT$(m,h+p)$ do in parallel
	begin
	  $D_m:=$COMPLEMENTA$(m,p)$;
	  $B_m \leftarrow B_{D_m}$
	end;
    for all $m$ where $0\leq m \leq 2^{3h}-1$ do in parallel
      $C_m:=A_m \ast B_m$;
    for $p:=2h$ to $3h-1$ do
      for all $m$ where $0\leq m \leq 2^{3h}-1$ do in parallel
	begin
	  $E_m:=$COMPLEMENTA$(m,p)$;
	  $D_m \leftarrow C_{E_m}$;
	  $C_m:=C_m+D_m$;
	end;
  end;
    
\end{lstlisting}
La procedura ha tempo pari a $O(\log n)$, utilizzando $n^3$ processori, otteniamo quindi un lavoro $O(n^3 \log n)$.\\
Vediamo ora l'esecuzione della procedura su di un ipercubo di $2^3=8$ processori per la moltiplciazione delle seguenti matrici 2 x 2.
$$
\left[
\begin{array}{cc}
 1 & 2 \\ 3 & 4
\end{array}
\right]
\left[
\begin{array}{cc}
 -5 & -6 \\ 7 & 8
\end{array}
\right]
=
\left[
\begin{array}{cc}
 9 & 10 \\ 13 & 14
\end{array}
\right]
$$
L'esecuzione per il calcolo \`e illustrata nella figura 2.11.\\
Inserire qui figura moltiplicazione matrici ipercubo.

\section{Trasformata di Fourier}
Vediamo ora un algoritmo per il calcolo della trasformata discrate di Fourier di un vettore reale $a=(a_0, a_1, ..., a_n)$, tale trasformata
\`e data dal vettore complesso $b=(b_0, b_1, ..., b_{n-1})$ tale che:
$$b_h=\sum_{k=0}^{n-1} a_k(\omega ^h)^k, \hspace{2cm}\texttt{per}\ 0\leq h \leq n-1$$
dove $\omega$ \`e la radice primitiva n-esima dell'unit\`a. Consideriamo di prendere $n$ potenza di 2 e vediamo l'algoritmo sequenziale ''divite \&
impera'', dove il problema \`e stato diviso in due sottoproblemi, come mostrato nella figura 2.12, che includono rispettivamente gli elementi di
posto pari e di posto dispari:
$$a^P(x)=\sum_{k=0}^{n/2-1}a_{2k}x^k, \hspace{2cm}a^d(x)=\sum_{k=0}^{n/2-1}a_{2k+1}x^k,$$ cos\`i che
$$a(x)=a^P(x)+a^D(x)$$
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{RETI/Partizionamento_Dati_FFT.eps}
\caption[Partizionamento dati FFT]{Partizionamento dei dati per FFT}\label{Partizionamento dati FFT}
\end{center}
\end{figure}
Vediamo di seguito lo pseudocodice per l'algoritmo FFT in sequenziale:
\begin{lstlisting}
procedure FFT($a$:polinomio-reale; $n$:integer; var $b$:polinomio-complesso);
  var $a^P, a^D$:polinomio-reale; $b^P,  b^D$:polinomio-complesso;
  begin
    if $n=1$ then $b_0:=a_0$
    else begin
      dividi il vettore $a$ $a^P=(a_0,a_2,...,a_{n-2})$ e $a^D=(a_1,a_3,...,a_{n-1})$;
      FFT$(a^P,n\ div\ 2,b^P)$; FFT$(a^D,n\ div\ 2,b^D)$;
      ricava $b$ ricombinando $b^P$ e $b^D$
    end
  end;
\end{lstlisting}
Osserviamo inoltre la ricombinazione dei risultati per l'algoritmo sequenziale, come illustrato nella figura 2.13 di seguito:
\begin{figure}[h]
\begin{center}
\includegraphics[width=10cm]{RETI/Ricombinazione_Calcolo_b1_per_FFT.eps}
\caption[Ricombinazione per calcolo di b1]{Ricombinazione per il calcolo di $b_1$ con FFT}\label{Ricombinazione calcolo b1}
\end{center}
\end{figure}
Osserviamo che si possono appaiare gli elementi $a_0,a_1,...,a_6,a_7$ nelle quattro coppie $(a_0,a_4),...,(a_3,a_7)$ che compaiono nel penultimo
livello dell'albero, allora \`e possibile calcolare direttamente le quattro trasformate $a_0-a_4,..,a_4-a_7$. Se poi si accoppiano nel modo giusto 
questi quattro valori, si possono calcolare le due trasformate al livello 1 dell'albero, ed infine da questi l'intera trasformata nella radice
dell'albero stesso; che, a questo punto, risulta essere esattamente lo schema di una butterfly!\\
Come vediamo nella figura 2.14











\begin{thebibliography}{90}             %crea l'ambiente bibliografia
\rhead[\fancyplain{}{\bfseries \leftmark}]{\fancyplain{}{\bfseries
\thepage}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%aggiunge la voce Bibliografia
                                        %   nell'indice
\addcontentsline{toc}{chapter}{Bibliografia}

\bibitem{K1} Alan Bertossi ''\textit{Algoritmi e Strutture Dati}'', UTET Libreria.

\end{thebibliography}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%non numera l'ultima pagina sinistra
\clearpage{\pagestyle{empty}\cleardoublepage}

\end{document}
